class Solution {
    unordered_map<int, int> memo;
public:
    int integerReplacement(int n) {
        // 时间O(logN) 空间O(logN)
        return dfs(n);
    }
 
    int dfs(long long n)
    {
        if(n == 1)
            return 0;
 
        if(memo[n] != 0)
            return memo[n];
        
        if(n % 2 == 0)
        {
            memo[n] = 1 + dfs(n / 2);
            return memo[n];
        }
        else
        {
            memo[n] = 1 + min(dfs(n - 1), dfs(n + 1));
            return memo[n];
        }
    }
};